//给出一个只有01的字符串数组，选出若干字符串，使得总共最多有m个0和n个1
//m,n相当于两个维度的背包，一个装0，一个装1，
//确定dp数组，是最多i个0和j个1的strs的最大子集的元素数量
//递推：看似是二维dp数组，但用的方法还是一维滚动数组，因为只有一个背包
//dp的两种来源：dp[i][j]和dp[i-zeros][j-ones]+1,取最大值
#include <vector>
#include <string>
#include <cmath>
using std::max;
using std::string;
using std::vector;
int findMaxForm(vector<string>& strs, int m, int n){
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    for(string str:strs){  //遍历物品
        int zeros=0,ones=0;
        for(char c: str){
            if(c=='0') zeros++;
            else ones++;
        }
        //倒序遍历，还是一维滚动数组的思想
        for(int j=n;j>=ones;j--){   //这两都是再遍历背包，而且可以颠倒因为这俩只是一个背包的不同维度
            for(int i=m;i>=zeros;i--)
                dp[i][j]=max(dp[i][j],dp[i-zeros][j-ones]+1);       //相当于一个物品价值为1，而且有两个维度的重量
        }
    }
    return dp[m][n];
}